#堆排序

lii = [174, 321, 399, 92, 566, 153, 226, 816, 856, 136]
def sift_sort(li,low,high):
    '''
    :param li: 列表
    :param low: 堆的根节点
    :param high: 堆的最后一个元素的位置
    :return:
    '''
    i = low # 最开始指向根节点
    j = 2*i + 1 #j开始是左孩子
    tmp = li[i] # 把堆顶存起来
    while j <= high: #只要j位置有数
        if j+1 <= high and li[j] < li[j+1]:#如果右孩子有且比较大
            j = j + 1
        if tmp < li[j]:
            li[i] = li[j]
            i = j #往下看一层
            j = 2 * i + 1
        else:
            break
    li[i] = tmp#把tmp放到叶子节点上

def heap_sort(li):
    n = len(li)
    for i in range(n//2 -1,-1,-1):
        #i表示建堆的时候调整的部分的下标
        sift_sort(li,i,n-1)
    #建堆完成
    for i in range(n-1,-1,-1):
        #i指向堆的最后一个元素
        li[0],li[i] = li[i],li[0]
        sift_sort(li,0,i-1)#i-1是新的high

heap_sort(lii)
print(lii)